机器学习算法可以分为三大类：监督学习、无监督学习和强化学习。
- 监督学习可用于一个特定的数据集（训练集）具有某一属性（标签），但是其他数据没有标签或者需要预测标签的情况。
- 无监督学习可用于给定的没有标签的数据集（数据不是预分配好的），目的就是要找出数据间的潜在关系。
- 强化学习位于这两者之间，每次预测都有一定形式的反馈，但是没有精确的标签或者错误信息。
有几种常见的关于监督学习和无监督学习的算法。比如决策树、朴素贝叶斯分类、最小二乘法（是一种计算线性回归的方法）。在这儿，主要介绍一种无监督学习的算法：奇异值分解（SVD）, 在线性代数中，SVD 是复杂矩阵的因式分解。
基础知识
矩阵的特征值和特征向量
设 A 是 n 阶矩阵，若存在数 $\lambda$ 及非零的 n 维列向量 $\nu$ ,使得
$$A\nu=\lambda\nu$$
成立，则称$\lambda$是矩阵 A 的特征值，称非零向量 $\nu$ 是矩阵 A 属于特征值 $\lambda$ 的特征向量
计算步骤：
- 计算 A 的特征多项式 $|\lambda I- A|$
- 判断特征方程 $|\lambda I- A| = 0$ 有没有根。由行列式计算可知，行列式$|\lambda I- A|$的值是n次多项式。如果没有根，则 A 没有特征值，从而也没有特征向量。如果 $|\lambda I- A|$ 有根，共有 n 个根（其中可能有复根，也可能有重根），这些根就是 A 的全部特征值。进行下一步
- 对于 A 的每一个特征值 $\lambda_j$ ，求解齐次线性方程组 $|\lambda_j I - A|X = 0$，则方程组的每一个非零解都是A的属于特征值$\lambda_j$的特征向量（说明有无穷多个）
举个例子：
设 $A=\left[ \begin{array}{cc} 1 & 2 \\ 2 & 4 \\ \end{array} \right]$
A的特征多项式为 $|\lambda I- A| = \left[ \begin{array}{cc} \lambda - 1 & -2 \\ -2 & \lambda - 4 \\ \end{array} \right] = \lambda(\lambda - 5)$
得到特征值 $\lambda_1 = 0, \lambda_2 = 5$
将 $\lambda_1$ 带入 $|\lambda_j I - A|X = 0$ :
$$|\lambda_j I - A| = \left[ \begin{array}{cc} -1 & -2 \\ -2 & -4 \\ \end{array} \right] = \left[ \begin{array}{cc} 1 & 2 \\ 0 & 0 \\ \end{array} \right]$$
故 $\lambda_1$ 的特征向量的基础解系为 $\left[ \begin{array}{cc} -2 & 1 \end{array} \right]$
将 $\lambda_2$ 带入 $|\lambda_j I - A|X = 0$ :
$$|\lambda_j I - A| = \left[ \begin{array}{cc} 4 & -2 \\ -2 & 1 \\ \end{array} \right] = \left[ \begin{array}{cc} -2 & 1 \\ 0 & 0 \\ \end{array} \right]$$
故 $\lambda_1$ 的特征向量的基础解系为 $\left[ \begin{array}{cc} 1 & 2 \end{array} \right]$
对角化分解
给定一个大小为$m\times m$的矩阵A（方阵），其对角化分解可以写成
$$A=U\Lambda U^{-1}$$
其中，U的每一列都是特征向量，$\Lambda$对角线上的元素是从大到小排列的特征值，若将U记作$U=\left( \vec{u}_1,\vec{u}_2,…,\vec{u}_m \right)$ ，则:
$$AU=A\left(\vec{u}_1,\vec{u}_2,…,\vec{u}_m\right)=\left(\lambda_1 \vec{u}_1,\lambda_2 \vec{u}_2,…,\lambda_m \vec{u}_m\right)$$
$$=\left(\vec{u}_1,\vec{u}_2,…,\vec{u}_m\right) \left[ \begin{array}{ccc} \lambda_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_m \\ \end{array} \right]$$
$$\Rightarrow AU=U\Lambda \Rightarrow A=U\Lambda U^{-1}$$
更为特殊的是，当矩阵A是一个对称矩阵时，则存在一个对称对角化分解，即
$$A=Q\Lambda Q^T$$
其中，Q的每一列都是相互正交的特征向量，且是单位向量，$\Lambda$对角线上的元素是从大到小排列的特征值。
当然，将矩阵Q记作$Q=\left(\vec{q}_1,\vec{q}_2,…,\vec{q}_m\right)$，则矩阵A也可以写成如下形式：
$$A=\lambda_1 \vec{q}_1\vec{q}_1^T+\lambda_2 \vec{q}_2\vec{q}_2^T+…+\lambda_m \vec{q}_m\vec{q}_m^T$$
举个例子：
如给定一个大小为$2\times 2$的矩阵$A=\left[ \begin{array}{cc} 2 & 1 \\ 1 & 2 \\ \end{array} \right]$，根据
$\left|\lambda I-A\right|=\left| \begin{array}{cc} \lambda-2 & -1 \\ -1 & \lambda-2 \\ \end{array} \right|=0$求得特征值为$\lambda_1=3，\lambda_2=1$，相应地，
$\vec{q}_1=\left[ \begin{array}{cc} \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} \\ \end{array} \right], \vec{q}_2=\left[ \begin{array}{cc} - \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} \\ \end{array} \right]$，则
$$A=\lambda_1 \vec{q}_1\vec{q}_1^T+\lambda_2 \vec{q}_2\vec{q}_2^T =\left[ \begin{array}{cc} 2 & 1 \\ 1 & 2 \\ \end{array} \right].$$
这样，我们就很容易地得到了矩阵A的对称对角化分解。
与奇异值分解的关系：对于正定对称矩阵而言，奇异值分解和对称对角化分解结果相同。
SVD的定义
设我们的矩阵A是一个m×n的矩阵，那么我们定义矩阵A的SVD为：
$$A=UΣV^T$$
其中U是一个m×m的矩阵，Σ是一个m×n的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，V是一个n×n的矩阵。U和V都是酉矩阵，即满足$U^T U=I,V^T V=I$
如何求取：
- 如果我们将A和A的转置做矩阵乘法，那么会得到m×m的一个方阵$AA^T$。既然$AA^T$是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：
$$(AA^T)\nu_i=λ_i \nu_i$$
这样我们就可以得到矩阵$AA^T$的m个特征值和对应的m个特征向量u了。将$AA^T$的所有特征向量张成一个m×m的矩阵U，就是我们SVD公式里面的U矩阵了。一般我们将U中的每个特征向量叫做A的左奇异向量。 - 将A的转置和A做矩阵乘法，那么会得到n×n的一个方阵$A^T A$。既然$A^T A$是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：
$$(A^T A)\nu_i=\lambda_i \nu_i$$
这样我们就可以得到矩阵 $A^T A$ 的n个特征值和对应的n个特征向量$\nu$了。将$A^T A$的所有特征向量张成一个n×n的矩阵V，就是我们SVD公式里面的V矩阵了。一般我们将V中的每个特征向量叫做A的右奇异向量。 - 由于Σ除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值σ就可以了。
$$A=UΣV^T ⇒ AV=UΣV^T V ⇒ AV=UΣ⇒ A\nu_i=σ_i u_i ⇒ σi=A\nu_i /u_i$$
特征值和奇异值满足此关系：$σ_i=\sqrtλ_i$ ,可以通过计算$A^T A$的特征值取平方根来求奇异值（注意，$AA^T$ 和 $A^T A$ 的特征值相同，证明链接 ）
求取步骤：
- 计算 $AA^T$ 和 $A^T A$；
- 分别计算 $AA^T$ 和 $A^T A$ 的特征向量及其特征值；
- $AA^T$ 的特征向量组成 U；而 $A^T A$ 的特征向量组成 V；
- 对 $AA^T$ 和 $A^T A$ 的非零特征值求平方根，对应上述特征向量的位置，填入 Σ 的对角元。
举个例子：
设 $A=\left[ \begin{array}{cc} 2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0 \\ \end{array} \right]$
首先，计算 $AA^T$:
$$AA^T = \left[ \begin{array}{cc} 2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0 \\ \end{array} \right] \left[ \begin{array}{cc} 2 & 1 & 0 & 0 \\ 4 & 3 & 0 & 0 \\ \end{array} \right] = \left[ \begin{array}{cc} 20 & 14 & 0 & 0 \\ 14 & 10 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right]$$
根据特征向量方程$|\lambda I- A| = 0$:
$$\left| \begin{array}{cc} \lambda - 20 & -14 & 0 & 0 \\ -14 & \lambda - 10 & 0 & 0 \\ 0 & 0 & \lambda & 0 \\ 0 & 0 & 0 & \lambda \\ \end{array} \right| = \left| \begin{array}{cc} \lambda - 20 & - 14 \\ - 14 & \lambda - 10 \\ \end{array} \right| \left| \begin{array}{cc} \lambda & 0 \\ 0 & \lambda \\ \end{array} \right| = 0$$
即: $ ((λ-20)(λ-10)−196)λ^2 = 0$， 得到特征值：$ λ_1=λ_2=0, λ_3=15+\sqrt 221≈29.866, λ_4=15− \sqrt 221≈0.134$
根据特征值代入原方程，可解得对应的特征向量。这些特征向量即作为列向量，形成矩阵:
$$U=\left[ \begin{array}{cc} 0.82 & -0.58 & 0 & 0 \\ 0.58 & 0.82 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]$$
同理可得：
$$V=\left[ \begin{array}{cc} 0.40 & -0.91 \\ 0.91 & 0.40 \\ \end{array} \right] $$
然后， Σ 上的对角线元素由 $AA^T$ 的特征值的算术平方根组成
$$Σ=\left[ \begin{array}{cc} 5.46 & 0 \\ 0 & 0.37 \\ 0 & 0 \\ 0 & 0 \\ \end{array} \right] $$
最后, 得到 A 的 SVD 分解：
$$\left[ \begin{array}{cc} 2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0 \\ \end{array} \right] ≈ \left[ \begin{array}{cc} 0.82 & -0.58 & 0 & 0 \\ 0.58 & 0.82 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right] \left[ \begin{array}{cc} 5.46 & 0 \\ 0 & 0.37 \\ 0 & 0 \\ 0 & 0 \\ \end{array} \right] \left[ \begin{array}{cc} 0.40 & -0.91 \\ 0.91 & 0.40 \\ \end{array} \right] $$
结果分析：
- 上述分解中会构建出一个矩阵∑，该矩阵只有对角元素，其他元素均为0(近似于0)。另一个惯例就是，∑的对角元素是从大到小排列的。这些对角元素称为奇异值。
- 奇异值与特征值(PCA 数据中重要特征)是有关系的。这里的奇异值就是矩阵 $AA^T$ 特征值的平方根。
- 普遍的事实：在某个奇异值的数目(r 个=>奇异值的平方和累加到总值的90%以上)之后，其他的奇异值都置为0(近似于0)。这意味着数据集中仅有 r 个重要特征，而其余特征则都是噪声或冗余特征。
SVD的性质
对于奇异值,它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。
也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：
其中k要比n小很多，也就是一个大的矩阵A可以用三个小的矩阵表示
- $U_{m×k}$,
- $Σ_{k×k}$
- $V^T_{k\times n}$
如下图所示，现在我们的矩阵A只需要灰色的部分的三个小矩阵就可以近似描述了。
由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。
奇异值分解的应用
- 隐性语义检索
隐性语义索引：矩阵 = 文档 + 词语
- 推荐系统
- 利用 SVD 从数据中构建一个主题空间。
- 再在该空间下计算其相似度。(从高维-低维空间的转化，在低维空间来计算相似度，SVD 提升了推荐系统的效率。)
- 图像压缩
例如：3232=1024 => 322+21+322=130(2*1表示去掉了除对角线的0), 几乎获得了10倍的压缩比。
补充知识
- 逆矩阵（inverse matrix）：
又称反矩阵。在线性代数中，给定一个n阶方阵 A，若存在一n阶方阵 B ，使得 $AB=BA=I_n$，其中 $I_n$ 为n阶单位矩阵，则称 A 是可逆的，且 B 是 A的逆矩阵，记作 $A^{-1}$。
只有方阵（n×n的矩阵）才可能有逆矩阵。若方阵 A 的逆矩阵存在，则称 A 为非奇异方阵或可逆方阵。
向量正交：指它们的内积等于零.治元前面已经讲过了。
单位矩阵：
n阶单位矩阵，是一个 $n * n$ 的方形矩阵，其主对角线元素为1，其余元素为0。单位矩阵以 $In$ 表示, 如果阶数可忽略，也可简记为 I（或者E）。 如:
$$
I{2}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}
$$- 行列式值得计算（必须是方阵）：
2 X 2 矩阵：
$$A = \left[ \begin{array}{cc} 2 & 1 \\ 1 & 2 \\ \end{array} \right]$$
